Buffers are used in many situations to provide elastic storage between processes or pairs of devices such as input/output devices. One type of buffer which is of particular interest in certain applications (for example, delay lines for digital filters and coefficient buffers for digital signal processing applications) is the so-called "circular" buffer, which is also called a "ring" buffer.
In general, buffers may be implemented in a number of ways. For example, a buffer may be realized as one or more hardware registers wired together; or it may simply be a bounded area in a larger memory which, under software control, is dedicated to performing the buffering operation. In either case, when the buffer is constrained to be of the circular variety, it is addressed in a very specific manner. Namely, an addressing algorithm forces an incrementing of the highest address in the buffer to wrap around to the lowest address, and a decrementing of the lowest address to wrap around to the highest address. Thus, in terms of addressing, a closed loop is formed.
Depending upon its use, the locations in a buffer may be accessed consecutively or in a random order or other non-consecutive pattern. Thus, the accessing of a buffer typically requires some mechanism for generating the successive buffer locations to be addressed. As each buffer address is generated, it is stored in a specific register or memory location (outside the buffer) which is reserved for that purpose. Such a register or memory location is referred to as a pointer register. Each time the buffer is to be accessed, the contents of the pointer register (i.e., the pointer) are modified in some way (e.g., by being incremented or decremented a specified amount), to establish the address for the next buffer-accessing operation.
Normally, a buffer has a finite size limitation, so some means must be employed to ensure that the address indicated by the pointer is always within the memory allocated to the buffer. Otherwise, an attempt will be made to write information to or read information from a memory location or register other than the one intended; if that happens, the integrity of the memory is lost. This can destroy the information which otherwise would have been in that location and cause the information which should have been written into a buffer location to be lost, or cause unpredictable system operation. One key to addressing a circular buffer, therefore, is to provide some mechanism for detecting an attempt to cause the buffer pointer to exceed the addressing boundaries of the buffer. If possible, some kind of adjustment can then be made to bring the address indicated by the pointer back within the range of addresses allocated to the buffer.
With a circular buffer, software techniques generally are employed to force the address following the highest address to be the lowest address in the buffer. Similarly, the next lower address which follows the lowest buffer address is constrained to be the highest buffer address. These software address-mapping techniques require several instruction cycles to perform the necessary address comparisons, arithmetic operations and replacement of the pointer's contents. Such software address mapping, however, is not fast enough for certain types of uses. Applications such as digital filters, Fast Fourier transforms, matrix manipulations, and other common digital signal processing routines require a very rapid generation of memory references. It is of little benefit to provide fast signal processing apparatus if the apparatus must spend a good part of its time idle, waiting to be supplied with addresses for reading or writing data.
A significant object of the present invention, therefore, is to provide fast, efficient address generation for a circular buffer.
Another object of the invention is to provide a simple, fast hardware system for generating addresses for accessing a circular buffer.
A further object of the invention is to provide address generation apparatus which allows successively accessed buffer locations to be separated by an arbitrary number of address locations.